1. Field of the Invention
The invention relates to methods and apparatus for generating logic outputs corresponding to several inputs, and more specifically to methods and apparatus for generating CARRY,SUM, AND, OR, INVERTING, NAND and NOR logic outputs.
2. Description of the Prior Art
Quantum devices like resonant tunneling transistors (RTT) have some distinctive speed advantages over conventional transistors. As functional densities of devices increase, there is an increasing pressure to reduce the device sizes. Quantum effects pose a major problem in shrinking conventional devices. As the devices become smaller and smaller, quantum interference occurs naturally and cannot be avoided. Quantum devices like resonant tunneling transistors (RTT) in fact make use of the quantum effects to operate. The quantum effects however cause negative differential resistance (NDR) characteristics. In the past NDR devices have not been found to be suitable for digital applications. Thus, it is desirable to make use of NDR device for digital applications. It is further desirable to develop a structure which is suitable to microminiaturize the NDR device.
Regularity and simplicity are the major features desired for Ultra Large Scale Integration (ULSI). AND, OR, NAND, NOR, CARRY, SUM and INVERTING logical circuits are the basic cells in all circuit designs. The conventional logic elements or cells are not regular which makes autorouting and ULSI very difficult.
One of the desired features of logical circuits is fast speed without increasing the complexity. It is desired to achieve logic and fundamental arithmetic operations at a fast speed while reducing the complexity.
Simplicity and fast speed have special application on binary addition which is a basic operation performed by all Logic and Arithmetic Operation Units.
Let x.sub.i and y.sub.i be binary inputs of bit i, z.sub.i is the sum of the bit i and c.sub.i is the carry out of the bit i, then z.sub.i and c.sub.i can be defined as follows: EQU Z.sub.i = X.sub.i + Y.sub.i + C.sub.i-l EQU C.sub.i = X.sub.i Y.sub.i + X.sub.i C.sub.i-l + Y.sub.i C.sub.i-l
The above equations indicate that sum z.sub.i of the ith bit depends on the i-lth bit carry out c.sub.i-l. If an adder has 64 bits and all C.sub.i (i=0, 1, 2, . . . , 63) ripple through all 63 stages, the c.sub.63 can be generated after 63 stages of delay which will slow the speed of the result of addition. Currently the carry look-ahead technique is the most common approach for achieving faster addition. In this strategy, the input carry bit of stage i is directly generated from the inputs of the preceding stages i-1, i-2, . . . ,i-m. An eight-bit carry look-ahead adder is shown in FIG 1. The carries can be expressed in terms of the propagate Pi=x.sub.i - y.sub.i and generate (g.sub.i =.multidot.y.sub.i) terms as EQU c.sub.i = g.sub.i + p.sub.i c.sub.i-l.
This can be solved recursively for the carries and, for example, in an eight bit adder the final carry out is: EQU C.sub.out = g.sub.7 + p.sub.7 g.sub.6 + p.sub.7 p.sub.6 g.sub.5 + p.sub.7 p.sub.6 g.sub.4 + p.sub.7 p.sub.6 p.sub.5 p.sub.4 g.sub.3 + p.sub.7 p.sub.6 p.sub.5 p.sub.4 p.sub.3 g.sub.2 + p.sub.7 p.sub.6 p.sub.5 p.sub.4 p.sub.3 p.sub.2 g.sub.1 + p.sub.7 p.sub.6 p.sub.5 p.sub.4 p.sub.3 p.sub.2 p.sub.1 g.sub.0 + p.sub.7 p.sub.6 p.sub.5 p.sub.4 p.sub.3 p.sub.2 p.sub.0 c.sub.in.
The complexity of the carry expressions increase as the number of look-ahead stages increases. This results in an increase in the fan-in requirements. The fan-in limitations thus limit the number of carry look-ahead stages to about m.ltoreq.8.
To perform a 64-bit addition, eight such 8-bit carry look-ahead adders may be used as shown in FIG. 2. A carry look-ahead addition is performed on each group of eight adjacent bits, and the output carry bit of each group is transferred to the input of its left neighbor. There is thus a ripple carry propagation between groups. To reduce the carry propagation delay, carry look-ahead addition is implemented using tree circuits which may consist of either standard gates with limited fan-in and fan-out, or carry look-ahead modules with a limited number of terminals. Though the speed is marginally increased in such implementations, the number of active devices and the complexity of the circuit increases substantially.
The adder circuit described in U.S. Pat. No. 3,280,316 is designed using the conventional equations for the sum and carry. As a result the circuit is very complex (refer to FIG. 9 of the patent). The carry generation will require at least six device (resonant tunneling diode, RTD) delays.